package com.rui.shangXueTang.huffman;

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

/**
 * @author : [锐神NO.3]
 * @version : [v1.0]
 * @className : HuffmanTree
 * @createTime : [2022/2/17 21:22]
 * @description : [描述该类的功能]
 */

@SuppressWarnings("all")
public class HuffmanTree {
    public static void main(String[] args) {
        int[] arr = {13,7,8,29,6,1};

        Node root = createHuffmanTree(arr);

        preSelect(root);
    }

    /**
     * 把数组转成赫夫曼树
     * @param arr 要转的数组
     * @return 返回根节点
     */
    public static Node createHuffmanTree(int[] arr) {
        List<Node> nodes = new ArrayList<>();

        //遍历数组,将元素转为节点对象
        for (int i : arr) {
            nodes.add(new Node(i));
        }

        while (nodes.size() > 1){
            //排序 从小到大
            Collections.sort(nodes);

            System.out.println("集合中的元素: " + nodes);

            Node leftNode = nodes.get(0);
            Node rightNode = nodes.get(1);

            //创建新的节点
            Node root = new Node(leftNode.value + rightNode.value);
            root.left = leftNode;
            root.right = rightNode;

            nodes.remove(leftNode);
            nodes.remove(rightNode);

            //添加新的节点
            nodes.add(root);
        }
        return nodes.get(0);
    }

    /**
     * 前序遍历
     */
    public static void preSelect(Node root){
        if(root != null){
            root.preSelect();
        }else {
            System.out.println("空树,无法前序遍历");
        }
    }
}
